package sample.xiaosong.violentrecursion;

import java.util.ArrayList;
import java.util.List;

/**
 * 打印一个字符串的所有组合
 */
public class PrintAllPermu {

    // 获取字符串所有排列
    public static List<String> getAll(String string) {
        List<String> result = new ArrayList<>();
        if (string.isEmpty()) {
            return result;
        }
        char[] chars = string.toCharArray();
        process(0, chars, result);
        result.sort(null);
        return result;
    }

    /**
     * 递归函数
     * @param i 字符串的第i个位置
     * @param chars 字符串数组
     * @param result 结果集
     */
    public static void process(int i, char[] chars, List<String> result) {
        // 边界条件 i到达了最后一个字符位置
        if (i == chars.length) {
            result.add(String.valueOf(chars));
        }
        // 记录当前字符是否已经访问过，避免重复
        boolean[] visited = new boolean[26];
        for (int j = i; j < chars.length; j++) {
            if (!visited[chars[j] - 'a']) {
                visited[chars[j] - 'a'] = true;
                // 对于任意i位置的字符，与其他所有j位置字符进行交换，就是它所有的可能性
                swap(i, j, chars);
                process(i + 1, chars, result);
                // 还原字符串
                swap(i, j, chars);
            }
        }
    }

    public static void swap(int i, int j, char[] chars) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

    public static void main(String[] args) {
        String str = "abc";
        List<String> result = getAll(str);
        for (String s : result) {
            System.out.println(s);
        }
    }
}
